A problem with existing communications and network systems is that sometimes it is desirable to ensure that messages sent from a sender are processed in the appropriate order by the receiver. In an asynchronous multi-hop network this can sometimes be a difficult task. For example, as shown in FIG. 1, a network environment 100 may include a set of messages S1 (104), S2 (108), that may travel from the sender S (102), via an intermediary I (106), to the receiver R (110):S—>I—>R
It is possible that the intermediary I, for any number of reasons, may re-order the messages it receives such that it forwards message S2 before it forwards message S1. The result is that receiver R would first receive message S2 and would then receive message S1, which is not the order that sender S had originally intended. In the general case the intermediary I can represent an entire network of intermediaries that could include for example generic intermediaries, firewalls, proxies, mail servers and any other system able to relay a message.
In order to work around this problem it is necessary for the sender S to mark its messages in such a manner that R can determine what their intended order is, and then process the messages in that order. A typical solution to this problem is to include an incrementing integer within S's messages such that the first message will start, typically at a value 0, and the next message will have the value 1, and so on. However, anyone implementing this solution quickly discovers that they have a context problem. For example, assume that S and R are participating in two different sets of message exchanges, the first regarding a purchase order and the second regarding a status request. These two exchanges are completely independent of each other and could be safely processed in parallel. However, by definition using a sequence number requires all of the messages to be processed serially, so it will not be possible to process them in parallel if only one integer is used on both conversations.
FIG. 2 shows an example of a message sequence 120 that includes an incrementing integer. For example, consider that the conversation regarding purchase orders generates messages SP1, SP2 and SP3. Consider also that the conversation regarding status requests generates messages SR1 and SR2. If a single message ID is being used, then the messages (122-130) will be stamped as they leave S, generating a sequence something like that shown in FIG. 2:SP1+1, SP2+2, SR1+3, SP3+4, SR2+5where the value “+N” in each message represents the sequence number for that particular message set.
In the above example, even though the SP messages and the SR messages could be processed in parallel (since they have nothing to do with each other), in practice they won't be because the sequence counter requires them to be generated in the order marked.
Another approach that some message ordering solutions take is to allow the sequence number to be associated with some form of conversation ID or similar identifier. FIG. 3 shows an example of a message sequence 140 that uses conversation ID's. When a conversation ID is being used, then the messages (142-150) will be stamped as they leave S, generating a sequence something like that shown in FIG. 3:SP1+C1+1, SP2+C1+2, SR1+C2+1, SP3+C1+3, SR2+C2+2where the value “+CN+Y” in each message represents the conversation ID and sequence number. The sequence number is ‘scoped’ to the conversation identifier so that it is no longer sufficient to specifyjust, e.g. ‘sequence ID 1’—it is now necessary to also specify “sequence ID 1 in conversation 1’. With the introduction of a conversation identifier it is possible for S and R to hold multiple, simultaneous conversations that can be processed completely independently of each other, and wherein each conversation is individually ordered.
At this point traditional messaging algorithms have to perform some cleanup work. Typically, they will specify what the first identifier number is (usually 0) so that the receiver knows when a conversation starts. They will also specify the maximum size of the integer used for the conversation ID. Finally, they will also specify how to behave when the integer rolls over, i.e. if the maximum integer size is 999 then what to do when 999 messages have been sent. The typical behavior is to start counting at 0 but to also include a flag that says “I am a rollover” to indicate that this isn't a ‘true’ 0 message but is the result of a rollover. Traditional systems will usually also include an explicit way to reset the counter, i.e. a message can be sent with a ‘0’ and a flag saying “I am resetting the counter to 0”. There is usually also some form of associated timer whose meaning is ‘if you don't receive another message in the conversation by time X then you can forget about the conversation.’ This is important in an asynchronous unreliable network where the receiver may fail/crash or the network may stop working, and in these instances it is undesirable to be stuck holding a lot of state that may never be used.
The traditional approaches described above suffer from a number of flaws. First of all, especially when applied to the world of Web Services, conversation IDs are a particularly bad idea. The Web Services world includes the concept of a service which is broken down into ports, which are themselves then broken down into operations. This structure demands three levels of abstraction and is difficult to manage because one must deal with various features applying at one or more combination of the levels. For example, if you want to configure that messages must be sent over SSL does that configuration apply at the service level, the port level, the operation level, or at some combination of the three levels? Dealing with these issues has proven extremely challenging for users and has made Web Services more difficult to use.
The use of conversations makes the situation worse by adding a fourth level to the hierarchy. Now the system must deal with service, port, operation, and conversation levels. If someone configures a security setting requiring SSL is that at the Service, Port, Operation or the Conversation level? To complicate matters—unlike the Service/Port/Operation hierarchy where each parent completely contains its children (for example, an operation belongs to exactly one port which belongs to exactly one service), the same is not true for conversations. Messages in a single conversation may need to occur across multiple operations or ports although typically they are required to be scoped to a single service. So the configuration issue gets even worse because not only do you have to configure information at four different levels of abstraction but one of those levels—the conversations level—itself crosses two other levels of abstraction.
The conversation model also fails when it comes to message ordering. For example, what happens if S and R need to sequence messages in two different conversations? What happens if messages within a conversation do not all need to be ordered? What happens if you need to sequence messages between more than two participants (for example A sends messages to B who sends messages to C) and there needs to be a global order? The Conversation plus sequence number model cannot deal with any of these scenarios.